package com.simon.study.algorithm.zheda;

import com.simon.study.algorithm.tree.TNode;

/**
 * <p>
 *
 * @author simon
 */
public class BTree {

    TNode root;

    public TNode find(int item){
        return find(root, item);
    }

    public static TNode find(TNode node, int item){
        if( node == null ){ return null; }

        if( item < node.getData() ){
            return find(node.getLeft(), item);
        }else if( item > node.getData() ){
            return find(node.getRight(), item);
        }else{
            return node;
        }
    }

    public static TNode findMin(TNode node){
        if(node == null){ return null; }

        else if(node.getLeft() != null){
            return findMin(node.getLeft());
        }
        else{ return node; }
    }

    public TNode findByLoop(int item){
        TNode node = root;
        while (node != null){
            if(item <  node.getData()){
                node = node.getLeft();
            }else if(item > node.getData()){
                node = node.getRight();
            }else{
                return node;
            }
        }
        return null;
    }

    public static TNode delete(TNode node, int item){
        if( node == null ){ return null; }
        else if(item  <  node.getData()){
            node.setLeft( delete(node.getLeft(), item)  );
        }
        else if( item > node.getData() ){
            node.setRight( delete(node.getRight(), item));
        }
        else{
            if(node.getLeft() != null && node.getRight() != null){
                TNode tar = findMin(node.getRight());
                node.setData( tar.getData() );
                node.setRight( delete(node.getRight(), tar.getData()) );
            }else{
                if(node.getRight() != null){
                    node = node.getRight();
                }else if(node.getLeft() != null){
                    node = node.getLeft();
                }else{
                    node = null;
                }
            }
        }
        return node;
    }

    public static TNode insert(TNode node, int item){
        if (node == null) {
            return new TNode(item);
        }else{
            if( item > node.getData() ){
                node.setRight( insert(node.getRight(), item) );
            }else{
                node.setLeft( insert(node.getLeft(),   item) );
            }
            return node;
        }
    }
}
